class Solution {
public:
    int largestRectangleArea(vector<int>& heights) { // 84 题
        stack<int> st;
        heights.push_back(-1); // 添加哨兵，确保所有元素都能被弹出
        int res = 0;
        int sz = heights.size();
        for (int i = 0; i < sz; ++i) 
        {
            while (!st.empty() && heights[i] < heights[st.top()]) 
            {
                int index = st.top();
                st.pop();
                int left = st.empty() ? -1 : st.top();
                res = max(res, (i - left - 1) * heights[index]);
            }
            st.push(i);
        }
        // 恢复原状（可选，取决于是否允许修改输入）
        heights.pop_back(); 
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) 
        {
            return 0; // 处理空输入
        }
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> heights(n); // 高度数组，大小为 n，与列数一致
        int res = 0;
        for (auto& row : matrix) 
        {
            // 计算以当前行 row 为底边的柱状图高度
            for (int j = 0; j < n; ++j) 
            {
                if (row[j] == '0') 
                    heights[j] = 0; // 遇到 '0'，高度归零
                else 
                    heights[j]++; // 遇到 '1'，高度累加
            }
            res = max(res, largestRectangleArea(heights)); // 复用 84 题解法
        }
        return res;
    }
};